package leetcode每日一题;

import java.util.HashMap;
import java.util.concurrent.locks.ReentrantLock;

/**
 * 1. 问题描述
 *      给定两个字符串s和t，判断它们是否是同构的。
 *      如果s中的字符可以被替换得到t，那么这两个字符串是同构的。
 *      所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。
 *      两个字符不能映射到同一个字符上，但字符可以映射自己本身。
 *
 * 2. 算法分析
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 字符串同构 {
    public static void main(String[] args) {

    }

    /**
     * 使用hashmap解决，算法下面有详细注释
     * @param s
     * @param t
     * @return
     */
    public static  boolean isIsomorphic1(String s, String t) {
        if(s.length() != t.length()) {return false;}
        HashMap<Character,Character> map = new HashMap<>();
        for(int i = 0; i < s.length(); i++) {
            if(map.containsKey(s.charAt(i))) {
                // 如果当前字符已经是map中的key了
                // 判断当前字符对应的key和t中索引i出的字符是否一致，如果不一致说明不同构
                if(map.get(s.charAt(i)) != t.charAt(i)) {
                    return false;
                }
            } else {
                // 注意此时不能直接将该key添加到map中
                // 我们需要重新扫描map，查看当前的key是否和已经出现在map中的key对应的value相同
                // 即检查是否有不同的key对应相同的valuet
                for(char key : map.keySet()) {
                    if(map.get(key) == t.charAt(i)) {
                        return false;
                    }
                }
                map.put(s.charAt(i),t.charAt(i));
            }
        }
        return true;
    }

    /**
     * 双hash实现 减少了上面单hash的嵌套循环
     * @param s
     * @param t
     * @return
     */
    public static boolean isIsomorphic2(String s, String t) {
        if(s.length() != t.length()) {return false;}
        // s中的字符为key，t的字符为value
        HashMap<Character,Character> mapS = new HashMap<>();
        // t中的字符为key，s中的字符为value
        HashMap<Character,Character> mapT = new HashMap<>();
        // 扫描s
        for(int i = 0; i < s.length(); i++) {
            char chs = s.charAt(i);
            char cht = t.charAt(i);
            if((mapS.containsKey(chs) && mapS.get(chs) != cht) || (mapT.containsKey(cht) && mapT.get(cht) != chs)) {
                return false;
            }
            mapS.put(chs,cht);
            mapT.put(cht,chs);
        }
        return true;
    }
}
